#include"sort.h"
void SortPrint(int* arr,int n)
{
	int i=0;
	for(;i<n;i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}
void InsertSort(int* arr,int n)
{
	int i=0;
	for(;i<n-1;i++)
	{
		int end=i;
		int tmp=arr[end+1];
		//end为已排序数字末尾，tmp储存待排序数
		//第一个循环遍历数组
		while(end>=0)
		{
			if(tmp<arr[end])
			{
			arr[end+1]=arr[end];
				end--;

			}else{
				break;
			}
		}
		arr[end+1]=tmp;//因为break前end--了
	}
}


void ShellSort(int*arr,int n)
{

	int gap=n;
	while(gap>1)
	{
		gap=gap/3+1;
		int i=0;
		for(;i<n-gap;i++)
		{
			int end=i;
			int tmp=arr[end+gap];
			//end为已排序数字末尾，tmp储存待排序数
			//第一个循环遍历数组
			while(end>=0)
			{		
				if(tmp<arr[end])
				{
					 arr[end+gap]=arr[end];
					 end-=gap;

				}else{
					break;
				}
			}
			arr[end+gap]=tmp;//因为break前end--了
		}	
	}

}






void Swap(HPDatatype* x, HPDatatype* y)
{
	HPDatatype tmp = *x; // 与元素类型一致
	*x = *y;
	*y = tmp;
}



void BubbleSort(int* a, int n)
{
 int exchange = 0;
 int i=0;
 for (; i < n; i++)
 {
	 int j=0;
 for (; j <n-i-1 ; j++)
 {
 if (a[j] > a[j + 1])
 {
 exchange = 1;
 Swap(&a[j], &a[j + 1]);
 }
 }
 if (exchange == 0)
 {
 break;
 }
 }
}


//hoare版本
int _QuickSort(int* arr,int left,int right)
{
	int keyi=left;
	++left;
	while(left<=right)//相遇点可能比基准值要大所以加上等号
	{
		//从左到右找比基准值要大的数据
		while(left<=right&&arr[left]<arr[keyi])//这里不加等号是为了优化算法
		{
			left++;
		}
		//从右到左找比基准值要小的数据
		while(left<=right&&arr[right]>arr[keyi])
		{
			right--;
		}
		if(left<=right)
		{
			Swap(&arr[left++],&arr[right--]);//必须leftright++--，不然遇到888这种情况，代码会无限循环
		}

	}
	Swap(&arr[keyi],&arr[right]);
	return right;
}

//前后指针法：cur探路，prev占位
int _QuickSort2(int*arr,int left,int right)
{
	int keyi=left;
	int prev=left;
	int cur=left+1;
	while(cur<=right)
	{
		if(arr[cur]<arr[keyi]&&++prev!=cur)
		{
			Swap(&arr[cur],&arr[prev]);//等同于prev左是小于keyi的数，cur右是大于keyi的数
		}
		cur++;
	}
	Swap(&arr[prev],&arr[keyi]);
	return keyi;
}

//挖坑法
int HoleSort(int* arr,int left,int right)
{

	int hole=left;
	int keyi=arr[hole];
	left++;
	while(left<right)
	{
		while(left<right&&arr[left]<keyi)
		{
			left++;
		}//找比基准值大的数据
		arr[hole]=arr[left];
		hole=left;
		
		while(left<right&&arr[right]>keyi)
		{
			right--;
		}//找比基准值小的数据
		arr[hole]=arr[right];
		hole=right;
	}
	arr[hole]=keyi;
	return keyi;
}



//三路划分法：对于相同数据出现频率较高时的优化
int ThreeWayPartition(int* arr, int left,int right)
{
	int cur=left+1;
	int keyi=left;
	int key=arr[keyi];
	while(right>cur)
	{
		if(arr[cur]<key)
		{
			Swap(&arr[left],&arr[keyi]);
			cur++;
			left++;
		}
		if(arr[cur]>key)
		{
			Swap(&arr[right],&arr[keyi]);
			right--;//这个时候不能cur++，因为不知道arr[cur]和key的大小关系
		}
		if(arr[cur]==key)
		{
			cur++;
		}
	}
	return keyi;
}

void QuickSort(int* arr,int left,int right)
{

	if(right<=left)
	{
		return;
	}
	//找基准值
	//int keyi=_QuickSort(arr,left,right);
	//int keyi=HoleSort(arr,left,right);
	int keyi=ThreeWayPartition(arr,left,right);
	QuickSort(arr,left,keyi-1);
	QuickSort(arr,keyi+1,right);
}



void QuickSortNonR(int*arr,int left,int right)
{
	ST st;
	STInit(&st);
	STPush(&st,right);
	STPush(&st,left);
	while(!STEmpty(&st))
	{
		int begin=STTop(&st);
		STPop(&st);
		int end=STTop(&st);
		STPop(&st);
		//取栈顶两次
		int keyi=begin;
		int prev=begin;
		int cur=prev+1;
		while(cur<=end)
		{
			if(arr[keyi]>arr[cur]&&prev++!=cur)
			{
				Swap(&arr[prev],&arr[cur]);
			}
			cur++;
		}
		Swap(&arr[keyi],&arr[prev]);
		if(keyi+1<end)
		{
			STPush(&st,end);
			STPush(&st,keyi+1);
		}
		if(begin<keyi-1)
		{
			STPush(&st,keyi-1);
			STPush(&st,begin);
		}
	}
	STDestroy(&st);
}


	


void AdjustDown(HPDatatype* arr, int parent, int n)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] <arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}



void HeapSort(int* arr, int n)//从小到大调整
{
	////给定arr建堆排序,升序降序
	////向下调整建堆：一棵一棵树调整（结点越来越多，所需挪动的层次越来越低）更优
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	// 向上调整建堆（结点越来越少，所需挪动的层次越来越多）
	
	//参考删除堆操作排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}


void SelectSort(int* arr,int n)
{
	int begin=0,end=n-1;
	while(begin<end)
	{
		int i=begin+1;//只遍历未排序的
		int mini=begin,maxi=begin;
		for(;i<=end;i++)
		{
			if(arr[mini]>arr[i])
			{
				mini=i;
			}	
			if(arr[maxi]<arr[i])
			{
				maxi=i;
			}
		}
		//注意特定情况
		if(maxi==begin)
		{
			maxi=mini;
		}
		Swap(&arr[mini],&arr[begin]);
		Swap(&arr[maxi],&arr[end]);
		begin++;
		end--;
	}

}


//归并
void _MergeSort(int*arr,int left,int right,int*tmp)
{
	//递归结束条件:分为单个数字
	if(left>=right)
	{
		return;
	}
	int mid=(left+right)/2;
	_MergeSort(arr,left,mid,tmp);
	_MergeSort(arr,mid+1,right,tmp);


	//合并排序数组
	int begin1=left,end1=mid;
	int begin2=mid+1,end2=right;
	int index=left;
	while(begin1<=end1&&begin2<=end2)
	{
		if(arr[begin1]<arr[begin2])
		{
			tmp[index]=arr[begin1++];
		}else{

			tmp[index]=arr[begin2++];
		}

		index++;
	}
	while(begin1<=end1)
	{
		tmp[index++]=arr[begin1++];
	}
	while(begin2<=end2)
	{
		tmp[index++]=arr[begin2++];
	}
	//将临时数组导入arr
	int i=left;
	for(;i<=right;i++)
	{
		arr[i]=tmp[i];
	}
}
void MergeSort(int*arr,int n)
{
	//申请临时数组储存结果
	int* tmp=(int*)malloc(sizeof(int)*n);
	if (tmp == NULL) 
	{
		 printf("内存分配失败！\n");
		return; // 处理内存分配失败的情况
	}
	_MergeSort(arr,0,n-1,tmp);
	free(tmp);
	tmp=NULL;
}


void MergeSortNonR(int* arr, int left,int right)
{
	int n=right-left+1;
	int* tmp=(int*)malloc(sizeof(int)*n);
	if(tmp==NULL)
	{
		perror("malloc,fail!");
		exit(1);
	}
	int gap=1;
	for(;gap<n;gap*=2)
	{
	
		int i=left;
		for(;i<n;i=i+gap*2)
		{
			
			int begin1=i,end1=i+gap-1;
			int begin2=i+gap,end2=i+2*gap-1;
			if(begin2>right)
			{
				break;
			}	
			//无右序列
			if(end2>right)
			{
				end2=n-1;
			}
			int index=begin1;
			while(end1>=begin1&&end2>=begin2)
			{
				if(arr[begin1]<arr[begin2])
				{
					tmp[index++]=arr[begin1++];
				}else{

					tmp[index++]=arr[begin2++];
				}
			}
			while(end1>=begin1)
			{	
				tmp[index++]=arr[begin1++];
			}
			while(end2>=begin2)
			{	
				tmp[index++]=arr[begin2++];
	
			}	
		memcpy(arr+i,tmp+i,sizeof(int)*(end2-i+1));
		}
	}
		
	tmp=NULL;

}

//非比较排序——计数排序
void CountSort(int* arr,int n)
{
	//先找到最大值最小值以确定申请数组范围大小
	int min=arr[0],max=arr[0];
	int i=0;
	for(;i<n;i++)
	{
		if(min>arr[i])
		{
			min=arr[i];
		}
		if(max<arr[i])
		{
			max=arr[i];
		}
	}
	int range=max-min+1;
	int* count=(int*)malloc(sizeof(int)*range);
	if(count==NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	memset(count,0,sizeof(int)*range);
	//也可以用calloc直接创建新数组并初始化
	i=0;
	for(;i<n;i++)
	{
		count[arr[i]-min]++;
	}
		
	//将下标出现次数输入原数组
		i=0;
		int index=0;
		for(;i<n;i++)
		{
		//遍历计数数组
		
		while(count[i]--)
		{
			arr[index++]=i+min;
		}
	}
}



void CreateNData()
{
	int n=1000000;
	// 造数据
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand()+i) % 1000000;
		fprintf(fin, "%d\n", x);
	 }
	fclose(fin);
}

int compare(const void *a, const void *b) {
    // 转换为 int* 再比较（针对 int 数组排序）
    int num1 = *(int*)a;
    int num2 = *(int*)b;
    return num1 - num2; // 升序排序（若需降序则返回 num2 - num1）
}
//返回实际读到的数据个数，没有数据返回0
int ReadNDataSortToFile(FILE* fout,int n,const char* file1)	
{
	int x=0;
	size_t i=0;
	int j=0;
	int* arr=(int*)malloc(sizeof(int)*n);
	if(arr==NULL)
	{
		perror("malloc fail!");
		return 0;
	}
	//读取n个数据，若遇见文件结束，读取了j个数据
	for(;i<n;i++)
	{
		if(fscanf(fout,"%d",&x)==EOF)
		{
			break;
		}
		arr[j++]=x;
	}
	if(j==0)
	{
		free(arr);
		return 0;
	}
	//排序
	qsort(arr,n,sizeof(int),compare);
	FILE* fin=fopen(file1,"w");
	if(fin==NULL)
	{
		perror("fopen fail!");
		return 0;
	}

	//写回file1文件
	int m=0;
	for(;m<j;m++)
	{
		fprintf(fin,"%d\n",arr[m]);
	}
	fclose(fin);
	free(arr);
	return j;
}


void MergeFile(const char* file1,const char* file2,const char*mfile)
{
	
	FILE* fout1=fopen(file1,"r");
	FILE* fout2=fopen(file2,"r");
	if(fout1==NULL)
	{
		perror("fopen fail!");
		return ;
	}
	
	if(fout2==NULL)
	{
		perror("fopen fail!");
		return ;
	}
	FILE* mfin=fopen(mfile,"w");
	if(mfin==NULL)
	{
		perror("fopen fail!");
		fclose(fout1); // 【修正】关闭 fout1 和 fout2
		fclose(fout2);
		return ;
	}
	int x1;
	int x2;
	int ret1=fscanf(fout1,"%d",&x1);
	int ret2=fscanf(fout2,"%d",&x2);
	//归并逻辑
	while(ret1!=EOF&&ret2!=EOF)
	{
		if(x1<x2)
		{
			fprintf(mfin,"%d\n",x1);
			ret1=fscanf(fout1,"%d",&x1);
		}else{

			fprintf(mfin,"%d\n",x2);
			ret2=fscanf(fout2,"%d",&x2);
		}
	}
	while(ret1!=EOF)
	{
		fprintf(mfin,"%d\n",x1);
		ret1=fscanf(fout1,"%d",&x1);
	}
	while(ret2!=EOF)
	{
		fprintf(mfin,"%d\n",x2);
		ret1=fscanf(fout1,"%d",&x2);
	}
	fclose(fout1);	
	fclose(fout2);	
	fclose(mfin);	
}

